package bit;

public class 错误的集合_645 {
    public int[] findErrorNums(int[] nums) {
        // nums 顺序是乱的   可以排序后和下标对比 最简单

        // 全组异或完后 再异或一遍 1 -> n
        // 重复的出现了3次  缺失的出现了一次  全部异或完就是  xor = a ^ a ^ a ^ b

        int xor = 0;

        int sum = 0; int total = (nums.length + 1) * nums.length / 2;
        for(int i = 0 ; i< nums.length; i++) {
            xor ^= nums[i];
            xor ^= (i+1);
            // 用来求和  从而在异或的两个值里边找重复的和缺失的
            sum += nums[i];
        }

        xor &= (-xor);
        // 每个数字出现了两次  除了 重复的 3次 缺失的 1次
        // 分组异或即可

        int miss = 0; int repeat = 0;
        for(int i = 0 ; i< nums.length; i++) {
            if((nums[i] & xor) == xor) {
                miss ^= nums[i];
            } else {
                repeat ^= nums[i];
            }

            if(((i+1) & xor) == xor) {
                miss ^= (i + 1);

            } else{
                repeat ^= (i + 1);
            }

        }
        // 用正负性判断哪个是repeat  哪个是 miss
        if((repeat - miss) == (sum - total) ) {
            return new int[]{repeat, miss};
        }
        return new int[]{miss, repeat};


    }
}
